Given an m x n matrix mat where every row is sorted in strictly increasing order, return the smallest common element in all rows.
If there is no common element, return -1.
Example 1:
Input: mat = [[1,2,3,4,5],[2,4,5,8,10],[3,5,7,9,11],[1,3,5,7,9]] Output: 5
Example 2:
Input: mat = [[1,2,3],[2,3,4],[2,3,5]] Output: 2
Constraints:
m == mat.lengthn == mat[i].length1 <= m, n <= 5001 <= mat[i][j] <= 104mat[i]is sorted in strictly increasing order.
Average Rating: 4.77 (31 votes)
Video Solution
Solution Article
The fact that every row is sorted in the increasing order tells us that there are no duplicates within a single row. So, if an element appears in all rows, it will appear exactly n times (where n is the number of rows).
We can count all elements, and then pick the smallest one that appears n times. This approach has a linear time complexity - at the cost of additional memory for storing counts.
Also, we can use a binary search to look elements up directly in the matrix. We won't need any additional memory, though this approach will be a bit slower.
Finally, we can track positions for each row. We will then repeatedly advance positions for smaller elements until all positions point to the common element - if there is one. The time complexity will be linear, and it will require less memory than when storing counts.
Approach 1: Count Elements
Iterate through all elements row-by-row and count each element. Since elements are constrained to [1...10000], we'll use an array of that size to store counts.
Then, iterate through the array left-to-right, and return the first element that appears n times. This is, by the way, how the counting sort works.
For an unconstrained problem, we'll need to use an ordered map to store counts.
Algorithm
-
Iterate
ithrough each row.-
Iterate
jthrough each column.- Increment
countfor elementmat[i][j].
- Increment
-
-
Iterate
kfrom1to10000.- If
count[k]equalsn, returnk.
- If
-
Return
-1.
Improved Solution
We can improve the average time complexity if we count elements column-by-column. This way, smaller elements will be counted first, and we can exit as soon as we get to an element that repeats n times.
For an unconstrained problem, we can use an unordered map (which should be faster than the ordered map as for the initial solution) if we count elements column-by-column.
Handling Duplicates
If elements are in non-decreasing order, we'll need to modify these solutions to properly handle duplicates. For example, we return 4 (initial solution) and 7 (improved solution) instead of 5 for this test case:
[[1,2,3,4,5],[5,7,7,7,7],[5,7,7,7,7],[1,2,4,4,5],[1,2,4,4,5]]
It's easy to modify these solutions to handle duplicates. Since elements in a row are sorted, we can skip the current element if it's equal to the previous one.
Complexity Analysis
-
Time complexity: O(nm), where n and m are the number of rows and columns.
-
Space complexity:
-
Constrained problem: O(10000)=O(1).
-
Unconstrained problem: O(k), where k is the number of unique elements.
-
Approach 2: Binary Search
We can go through each element in the first row, and then use binary search to check if that element exists in all other rows.
Algorithm
-
Iterate through each element in the first row.
-
Initialize
foundto true. -
For each row:
-
Use binary search to check if the element exists.
-
If it does not, set
foundto false and exit the loop.
-
-
If
foundis true, return the element.
-
-
Return
-1.
In the solution above, we always search the entire row. We can improve the average time complexity if we start the next search from the position returned by the previous search. We can also return -1 if all elements in the row are smaller than value we searched for.
Note that
lower_boundin C++ returns the position of first element that is equal (if exists) or greater than the searched value. In Java,binarySearchreturns a positive index if the element exists, or(-insertion_point - 1), whereinsertion_pointis also the position of the next greater element. In both cases, it points past the last element if all elements are smaller than the value being searched for.
Handling Duplicates
Since we search for an element in each row, this approach works correctly if there are duplicates.
Complexity Analysis
-
Time complexity: O(mnlogm)
-
We iterate through m elements in the first row.
-
For each element, we perform the binary search n times over m elements.
-
-
Space complexity:
-
Original solution: O(1).
-
Improved solution: O(n) to store search positions for all rows.
-
Approach 3: Row Positions
We can enumerate elements in all rows in the sorted order, as described in approach 2 for the 23. Merge k Sorted List problem.
For each row, we track the position of the current element starting from zero. Then, we find the smallest element among all positions, and advance the position for the corresponding row. We find our answer when all positions point to elements with the same value.
For this problem, however, we do not need to enumerate elements in the perfectly sorted order. We can determine the largest element among all positions and skip smaller elements in all other rows.
Algorithm
-
Initialize row positions, current max and counter with zeros.
-
For each row:
-
Increment the row position until the value is equal or greater than the current max.
- If we reach the end of the row, return
-1.
- If we reach the end of the row, return
-
If the value equals the current max, increase the counter.
- Otherwise, reset the counter to
1and update the current max.
- Otherwise, reset the counter to
-
If the counter is equal to
n, return the current max.
-
-
Repeat step 2.
Handling Duplicates
Since we take one element from each row, this approach works correctly if there are duplicates.
Complexity Analysis
-
Time complexity: O(nm); we iterate through all nm elements in the matrix in the worst case.
-
Space complexity: O(n) to store row indices.
Improved Solution
We can use a binary search to advance positions, like in Improved Solution for Approach 2.
While it can certantly improve the runtime, the worst case time complexity will be O(mnlogm), which is a downgrade from O(nm) for the simple increment. The reason is that, if we need to advance row positions one-by-one, the binary search will still take O(logm) to find that very next value.
To optimize for the worst-case scenario, we can use the one-sided binary search (also known as the meta binary search), where we iterativelly double the distance from out position. The number of operations performed by such search will not exceed the distance between the original and resulting position, bringing the time complexity back to O(nm).
Last Edit: March 23, 2021 6:48 PM
Approach 4, use set intersection:
class Solution:
def smallestCommonElement(self, mat: List[List[int]]) -> int:
M = iter(mat)
S = set(next(M))
for row in M:
S &= set(row)
return min(S, default=-1)
October 27, 2019 8:24 AM
Nice article. Can we use something like merge sort, we divide rows into two halves each time. We can merge, when we have upper_row, mid_row, and lower_row. After finish counting range [upper_row, mid_row) and [mid_row, lower_row], we can merge results by checking mid_row and lower_row. We preserve the counting for each element in the last row of a range. It is totally fine if some elements in row mid_row-1 is missing in row mid_row. Missing elements cannot exist in each row!!
I think we need an auxiliary 2D array (implying O(R*C) space complexity), and each array element save the value of the original arguments, and the value's count in the "range". If elements in a row don't repeat, since the merge time only takes O(C), I think its time complexity is O(C*logR). Am I right?
Ruby FTW:
def smallest_common_element(mat)
mat.reduce(&:intersection).min || -1
end
March 24, 2021 11:27 AM
This is a great problem and now this article is even better, thanks for sharing!
January 30, 2020 8:40 PM
Should the worst-case time complexity for the 3rd solution be O(RClogC)? Where R and C are row and column numbers of mat.
For each row we use binary search to advance the pointer to first position greater than or equal to cur_max, but it is not necessarily faster than advancing the pointer by linear scanning, e.g. we can spend log(C) time on binary search but only advance the pointer by 1. One such worst case could be mat[i][j] = i + j * R.
In approach 3 why do we use while(true) condition, can anyone pls explain
Last Edit: July 11, 2020 11:36 AM
I believe the space complexity for the 1st approach should be O(maximum integer in entire matrix) . I'm not sure why they say it should be O(k), the number of unique elements. My solution has the same runtime as the 1st approach, but with O(R) space complexity, R meaning the length of a row.
You don't have any submissions yet.
xxxxxxxxxxclass Solution {public: int smallestCommonElement(vector<vector<int>>& mat) { }};